#include <cstddef>
#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NODE 10

typedef struct Node {
  int key;
  Node *lchild, *rchild;
} Node;

Node *queue[MAX_NODE + 5];
int head, tail, tot = 0;

Node *getNewNode(int key) {
  Node *p = (Node *)malloc(sizeof(Node));
  p->key = key;
  p->lchild = p->rchild = NULL;
  return p;
}

void clear(Node *root) {
  if (root == NULL)
    return;
  clear(root->lchild);
  clear(root->rchild);
  free(root);
  return;
}

Node *insertNode(Node *root, int key) {
  if (root == NULL)
    return getNewNode(key);
  if (rand() % 2)
    root->lchild = insertNode(root->lchild, key);
  else
    root->rchild = insertNode(root->rchild, key);
  return root;
}

void bfs(Node *root){
    if(root == NULL) return;
    head = tail = 0;
    queue[tail++] = root;
    while(head < tail){
        Node *node = queue[head];
        printf("\nnode: %d\n", node->key);
        if(node->lchild) {
            queue[tail++] = node->lchild;
            printf("\t%d->%d (left)\n", node->key, node->lchild->key);
            }
        if(node->rchild) {
            queue[tail++] = node->rchild;
            printf("\t%d->%d (right)\n", node->key, node->rchild->key);
        }
        head++;
    }
    return;
}

void dfs(Node *root){
    if(root == NULL) return;
    int start, end;
    tot++;
    start = tot;
    if(root->lchild) dfs(root->lchild);
    if(root->rchild) dfs(root->rchild);
    tot++;
    end = tot;
    printf("%d: [%d, %d]\n", root->key, start, end);
    return;
}

int main() {
  srand(time(0));
  Node *root = NULL;
  for(int i = 0; i < MAX_NODE ; i++){
    root = insertNode(root, rand() % 100);
  }
  bfs(root);
  dfs(root);
  clear(root);
  
  return 0;
}
